package org.mm.proxycache.util.collections;

/*
 * @(#)ConcurrentSkipListSet.java   1.4 06/05/10
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;

import sun.misc.Unsafe;

/**
 * A scalable concurrent {@link NavigableSet} implementation based on a
 * {@link ConcurrentSkipListMap}. The elements of the set are kept sorted
 * according to their {@linkplain Comparable natural ordering}, or by a
 * {@link Comparator} provided at set creation time, depending on which
 * constructor is used.
 *
 * <p>
 * This implementation provides expected average <i>log(n)</i> time cost for
 * the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt> operations
 * and their variants. Insertion, removal, and access operations safely execute
 * concurrently by multiple threads. Iterators are <i>weakly consistent</i>,
 * returning elements reflecting the state of the set at some point at or since
 * the creation of the iterator. They do <em>not</em> throw {@link
 * ConcurrentModificationException}, and may proceed concurrently with other
 * operations. Ascending ordered views and their iterators are faster than
 * descending ones.
 *
 * <p>
 * Beware that, unlike in most collections, the <tt>size</tt> method is
 * <em>not</em> a constant-time operation. Because of the asynchronous nature
 * of these sets, determining the current number of elements requires a
 * traversal of the elements. Additionally, the bulk operations <tt>addAll</tt>,
 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>containsAll</tt> are
 * <em>not</em> guaranteed to be performed atomically. For example, an
 * iterator operating concurrently with an <tt>addAll</tt> operation might
 * view only some of the added elements.
 *
 * <p>
 * This class and its iterators implement all of the <em>optional</em> methods
 * of the {@link Set} and {@link Iterator} interfaces. Like most other
 * concurrent collection implementations, this class does not permit the use of
 * <tt>null</tt> elements, because <tt>null</tt> arguments and return values
 * cannot be reliably distinguished@SuppressWarnings("unchecked") from the
 * absence of elements.
 *
 * <p>
 * This class is a member of the <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author Doug Lea
 * @param <E>
 *            the type of elements maintained by this set
 * @since 1.6
 */
@SuppressWarnings( "unchecked" )
public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable,
        java.io.Serializable
{
    
    private static final long serialVersionUID = -2479143111061671589L;
    
    /**
     * The underlying map. Uses Boolean.TRUE as value for each element. This
     * field is declared final for the sake of thread safety, which entails some
     * ugliness in clone()
     */
    private final ConcurrentNavigableMap<E, Object> m;
    
    /**
     * Constructs a new, empty set that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     */
    public ConcurrentSkipListSet()
    {
        m = new ConcurrentSkipListMap<E, Object>();
    }
    
    /**
     * Constructs a new, empty set that orders its elements according to the
     * specified comparator.
     *
     * @param comparator
     *            the comparator that will be used to order this set. If
     *            <tt>null</tt>, the {@linkplain Comparable natural ordering}
     *            of the elements will be used.
     */
    public ConcurrentSkipListSet( Comparator<? super E> comparator )
    {
        m = new ConcurrentSkipListMap<E, Object>( comparator );
    }
    
    /**
     * Constructs a new set containing the elements in the specified collection,
     * that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     *
     * @param c
     *            The elements that will comprise the new set
     * @throws ClassCastException
     *             if the elements in <tt>c</tt> are not {@link Comparable},
     *             or are not mutually comparable
     * @throws NullPointerException
     *             if the specified collection or any of its elements are null
     */
    public ConcurrentSkipListSet( Collection<? extends E> c )
    {
        m = new ConcurrentSkipListMap<E, Object>();
        addAll( c );
    }
    
    /**
     * Constructs a new set containing the same elements and using the same
     * ordering as the specified sorted set.
     *
     * @param s
     *            sorted set whose elements will comprise the new set
     * @throws NullPointerException
     *             if the specified sorted set or any of its elements are null
     */
    public ConcurrentSkipListSet( SortedSet<E> s )
    {
        m = new ConcurrentSkipListMap<E, Object>( s.comparator() );
        addAll( s );
    }
    
    /**
     * For use by submaps
     */
    ConcurrentSkipListSet( ConcurrentNavigableMap<E, Object> m )
    {
        this.m = m;
    }
    
    /**
     * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt> instance.
     * (The elements themselves are not cloned.)
     *
     * @return a shallow copy of this set
     */
    @Override
    public ConcurrentSkipListSet<E> clone()
    {
        ConcurrentSkipListSet<E> clone = null;
        try
        {
            clone = (ConcurrentSkipListSet<E>) super.clone();
            clone.setMap( new ConcurrentSkipListMap( m ) );
        }
        catch (CloneNotSupportedException e)
        {
            throw new InternalError();
        }
        
        return clone;
    }
    
    /* ---------------- Set operations -------------- */

    /**
     * Returns the number of elements in this set. If this set contains more
     * than <tt>Integer.MAX_VALUE</tt> elements, it returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * <p>
     * Beware that, unlike in most collections, this method is <em>NOT</em> a
     * constant-time operation. Because of the asynchronous nature of these
     * sets, determining the current number of elements requires traversing them
     * all to count them. Additionally, it is possible for the size to change
     * during execution of this method, in which case the returned result will
     * be inaccurate. Thus, this method is typically not very useful in
     * concurrent applications.
     *
     * @return the number of elements in this set
     */
    @Override
    public int size()
    {
        return m.size();
    }
    
    /**
     * Returns <tt>true</tt> if this set contains no elements.
     *
     * @return <tt>true</tt> if this set contains no elements
     */
    @Override
    public boolean isEmpty()
    {
        return m.isEmpty();
    }
    
    /**
     * Returns <tt>true</tt> if this set contains the specified element. More
     * formally, returns <tt>true</tt> if and only if this set contains an
     * element <tt>e</tt> such that <tt>o.equals(e)</tt>.
     *
     * @param o
     *            object to be checked for containment in this set
     * @return <tt>true</tt> if this set contains the specified element
     * @throws ClassCastException
     *             if the specified element cannot be compared with the elements
     *             currently in this set
     * @throws NullPointerException
     *             if the specified element is null
     */
    @Override
    public boolean contains( Object o )
    {
        return m.containsKey( o );
    }
    
    /**
     * Adds the specified element to this set if it is not already present. More
     * formally, adds the specified element <tt>e</tt> to this set if the set
     * contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>. If
     * this set already contains the element, the call leaves the set unchanged
     * and returns <tt>false</tt>.
     *
     * @param e
     *            element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     *         element
     * @throws ClassCastException
     *             if <tt>e</tt> cannot be compared with the elements
     *             currently in this set
     * @throws NullPointerException
     *             if the specified element is null
     */
    @Override
    public boolean add( E e )
    {
        return m.putIfAbsent( e, Boolean.TRUE ) == null;
    }
    
    /**
     * Removes the specified element from this set if it is present. More
     * formally, removes an element <tt>e</tt> such that <tt>o.equals(e)</tt>,
     * if this set contains such an element. Returns <tt>true</tt> if this set
     * contained the element (or equivalently, if this set changed as a result
     * of the call). (This set will not contain the element once the call
     * returns.)
     *
     * @param o
     *            object to be removed from this set, if present
     * @return <tt>true</tt> if this set contained the specified element
     * @throws ClassCastException
     *             if <tt>o</tt> cannot be compared with the elements
     *             currently in this set
     * @throws NullPointerException
     *             if the specified element is null
     */
    @Override
    public boolean remove( Object o )
    {
        return m.remove( o, Boolean.TRUE );
    }
    
    /**
     * Removes all of the elements from this set.
     */
    @Override
    public void clear()
    {
        m.clear();
    }
    
    /**
     * Returns an iterator over the elements in this set in ascending order.
     *
     * @return an iterator over the elements in this set in ascending order
     */
    @Override
    public Iterator<E> iterator()
    {
        return m.navigableKeySet().iterator();
    }
    
    /**
     * Returns an iterator over the elements in this set in descending order.
     *
     * @return an iterator over the elements in this set in descending order
     */
    public Iterator<E> descendingIterator()
    {
        return m.descendingKeySet().iterator();
    }
    
    /* ---------------- AbstractSet Overrides -------------- */

    /**
     * Compares the specified object with this set for equality. Returns
     * <tt>true</tt> if the specified object is also a set, the two sets have
     * the same size, and every member of the specified set is contained in this
     * set (or equivalently, every member of this set is contained in the
     * specified set). This definition ensures that the equals method works
     * properly across different implementations of the set interface.
     *
     * @param o
     *            the object to be compared for equality with this set
     * @return <tt>true</tt> if the specified object is equal to this set
     */
    @Override
    public boolean equals( Object o )
    {
        // Override AbstractSet version to avoid calling size()
        if ( o == this )
            return true;
        if ( !(o instanceof Set) )
            return false;
        Collection<?> c = (Collection<?>) o;
        try
        {
            return containsAll( c ) && c.containsAll( this );
        }
        catch (ClassCastException unused)
        {
            return false;
        }
        catch (NullPointerException unused)
        {
            return false;
        }
    }
    
    /**
     * Removes from this set all of its elements that are contained in the
     * specified collection. If the specified collection is also a set, this
     * operation effectively modifies this set so that its value is the
     * <i>asymmetric set difference</i> of the two sets.
     *
     * @param c
     *            collection containing elements to be removed from this set
     * @return <tt>true</tt> if this set changed as a result of the call
     * @throws ClassCastException
     *             if the types of one or more elements in this set are
     *             incompatible with the specified collection
     * @throws NullPointerException
     *             if the specified collection or any of its elements are null
     */
    @Override
    public boolean removeAll( Collection<?> c )
    {
        // Override AbstractSet version to avoid unnecessary call to size()
        boolean modified = false;
        for ( Object name : c )
            if ( remove( name ) )
                modified = true;
        return modified;
    }
    
    /* ---------------- Relational operations -------------- */

    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if the specified element is null
     */
    public E lower( E e )
    {
        return m.lowerKey( e );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if the specified element is null
     */
    public E floor( E e )
    {
        return m.floorKey( e );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if the specified element is null
     */
    public E ceiling( E e )
    {
        return m.ceilingKey( e );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if the specified element is null
     */
    public E higher( E e )
    {
        return m.higherKey( e );
    }
    
    public E pollFirst()
    {
        Map.Entry<E, Object> e = m.pollFirstEntry();
        return e == null ? null : e.getKey();
    }
    
    public E pollLast()
    {
        Map.Entry<E, Object> e = m.pollLastEntry();
        return e == null ? null : e.getKey();
    }
    
    /* ---------------- SortedSet operations -------------- */

    public Comparator<? super E> comparator()
    {
        return m.comparator();
    }
    
    /**
     * @throws NoSuchElementException
     *             {@inheritDoc}
     */
    public E first()
    {
        return m.firstKey();
    }
    
    /**
     * @throws NoSuchElementException
     *             {@inheritDoc}
     */
    public E last()
    {
        return m.lastKey();
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code fromElement} or {@code toElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> subSet( E fromElement, boolean fromInclusive, E toElement,
            boolean toInclusive )
    {
        return new ConcurrentSkipListSet<E>( m.subMap( fromElement, fromInclusive, toElement,
                toInclusive ) );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code toElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> headSet( E toElement, boolean inclusive )
    {
        return new ConcurrentSkipListSet<E>( m.headMap( toElement, inclusive ) );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code fromElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> tailSet( E fromElement, boolean inclusive )
    {
        return new ConcurrentSkipListSet<E>( m.tailMap( fromElement, inclusive ) );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code fromElement} or {@code toElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> subSet( E fromElement, E toElement )
    {
        return subSet( fromElement, true, toElement, false );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code toElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> headSet( E toElement )
    {
        return headSet( toElement, false );
    }
    
    /**
     * @throws ClassCastException
     *             {@inheritDoc}
     * @throws NullPointerException
     *             if {@code fromElement} is null
     * @throws IllegalArgumentException
     *             {@inheritDoc}
     */
    public NavigableSet<E> tailSet( E fromElement )
    {
        return tailSet( fromElement, true );
    }
    
    /**
     * Returns a reverse order view of the elements contained in this set. The
     * descending set is backed by this set, so changes to the set are reflected
     * in the descending set, and vice-versa.
     *
     * <p>
     * The returned set has an ordering equivalent to
     * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
     * The expression {@code s.descendingSet().descendingSet()} returns a view
     * of {@code s} essentially equivalent to {@code s}.
     *
     * @return a reverse order view of this set
     */
    public NavigableSet<E> descendingSet()
    {
        return new ConcurrentSkipListSet( m.descendingMap() );
    }
    
    // Support for resetting map in clone
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long mapOffset;
    static
    {
        try
        {
            mapOffset = unsafe.objectFieldOffset( ConcurrentSkipListSet.class
                    .getDeclaredField( "m" ) );
        }
        catch (Exception ex)
        {
            throw new Error( ex );
        }
    }
    
    private void setMap( ConcurrentNavigableMap<E, Object> map )
    {
        unsafe.putObjectVolatile( this, mapOffset, map );
    }
    
}
